package afi;


import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class ArraySearch {

	/**
	 * Problem 1.2 in AFI: find first occurrence of the given key in sorted array A
	 */
	public int searchFirst(int[] a, int key){
		int l=0, h=a.length-1, m;
		while(l<=h){
			m = l + (h-l)/2;
			if(a[m] == key)
				return findFirst(a, key, l, m);
			if(a[m] < key)
				l = m+1;
			else
				h = m;
		}
		return -1;
	}
	
	private int findFirst(int[] a, int v, int l, int h){
		int m;
		while(l < h){
			m = l + (h-l)/2;
			if(a[m] != v)
				l=m+1;
			else
				h=m;
		}
		return h;
	}
	
	
	
	/**
	 * Problem 1.3 in AFI: find first element larger than the given key in sorted array A
	 */
	public int searchFirstLarger(int[] a, int key){
		int l=0, h=a.length-1, m;
		while(l<=h){
			m = l+(h-l)/2;
			if(a[m] == key)
				return findLarger(a, key, m, h);
			if(a[m] < key)
				l = m+1;
			else
				h = m-1;
		}
		return -1;
	}
	
	private int findLarger(int[] a, int key, int low, int high){
		int m;
		while(low < high-1){
			m = low + (high-low)/2;
			if(a[m] > key)
				high = m;
			else
				low = m;
		}
		return high;
	}
	
	
	/**
	 * Problem 1.4 in AFI: find i such that A[i] = i, where A contains sorted distinct integers
	 */
	public int findEqualIndex(int[] a){
		int l=0, h=a.length-1, m;
		while(a[l]<=l && a[h]>=h){
			m = l+(h-l)/2;
			if(a[m]==m)
				return m;
			if(a[m]<m)
				l=m+1;
			else
				h=m-1;
		}
		return -1;
	}
	
	
	/**
	 * Tests
	 */
	public static void main(String[] args) {
		
		// Test for 1.2
		int[] a = new int[1000];
		int i;
		for(i=0; i<1000; i++)
			a[i] = (int)(Math.random()*10);
		
		Arrays.sort(a);
		
		for(i=0; i<1000; i++){
			if(a[i] == 4)
				break;
		}
		
		ArraySearch arraySearch = new ArraySearch();
		
		//System.out.println(arraySearch.searchFirst(a, 4) == i);
		
		
		// Test for 1.3
		for(i=0; i<1000; i++){
			if(a[i] > 2)
				break;
		}
		
		//System.out.println(arraySearch.searchFirstLarger(a, 2) == i);
		
		
		//Test for 1.4
		for(int test = 1; test<=100; test++){
			
			Set<Integer> list = new HashSet<Integer>();
			for(i=0; i<100; i++){
				list.add((int)(Math.random()*1000));
			}
			
			a = new int[list.size()];
			i=0;
			for(Integer x : list){
				a[i] = x;
				i++;
			}
			Arrays.sort(a);
			int r = arraySearch.findEqualIndex(a);
			if(r>-1)
				System.out.println(r + "\t" + a[arraySearch.findEqualIndex(a)]);
			else{
				boolean correct = true;
				for(i=0; i<a.length; i++){
					if(a[i] == i)
						correct = false;
				}
				System.out.println(correct);
			}
			
		}
	}
}
